#include <iostream>
#include <ctime>
#include <algorithm>
#include <vector>
#include "user_algor.h"

using namespace std;
void time_test0();
void time_test1();
void time_test2();
void time_test3();


int main()
{
    time_test3();
	return 0;
}

void time_test0()
{
	vector<int> a;
	int step = 10;
	/* 1ms clock one time*/
	double clocks = double(CLOCKS_PER_SEC) / 1000;
	
	cout << "The worst-case time, in milliseconds, are" << endl;
	cout << "n \t Time" << endl;
	
	for (int n = 0; n <= 1000; n += step) {
		// the badest states
		for (int i = 0; i < n; i++)
			a.push_back(n - i);
		
		clock_t startTime = clock();
		insertSort(a);
		double elapsed = (clock() - startTime)/clocks;
		
		cout << n << '\t' << elapsed << endl;
		if (n == 100)
			step = 100;
	}    
}

void time_test1()
{
	int a[1000], step = 10;
	/* 1ms clock one time*/
	double clocks = double(CLOCKS_PER_SEC) / 1000;
	
	cout << "The worst-case time, in milliseconds, are" << endl;
	cout << "n \t Time" << endl;
	
	for (int n = 0; n <= 1000; n += step) {
		// the badest states
		for (int i = 0; i < n; i++)
			a[i] = n - i;
		
		clock_t startTime = clock();
		insertSort(a, n);
		double elapsed = (clock() - startTime)/clocks;
		
		cout << n << '\t' << elapsed << endl;
		if (n == 100)
			step = 100;
	}    
}

void time_test2()
{
	int a[1000], temp[1000], step = 10;
	/* 1ms clock one time*/
	double clocks = double(CLOCKS_PER_SEC) / 1000;
	
	cout << "The worst-case time, in milliseconds, are" << endl;
	cout << "n \tRepetitions \tTotal Ticks \tTime Per Sort" << endl;
	
	for (int n = 0; n <= 1000; n += step) {
		long numOfRepetitions = 0;
		clock_t startTime = clock();
		do{
			numOfRepetitions ++;
            
			// the badest states
		    for (int i = 0; i < n; i++)
			    a[i] = n - i;
			
			bucketSort(a, n);
		}while(clock() - startTime < 1000);

		double elapsed = (clock() - startTime)/clocks;	
		cout << n << '\t' << numOfRepetitions << '\t' << elapsed 
		     << '\t' << elapsed/numOfRepetitions << endl;
		if (n == 100)
			step = 100;			    
	}
}


void time_test3()
{
	int **a, **b, **c, step = 10;
	/* 1ms clock one time*/
	double clocks = double(CLOCKS_PER_SEC) / 1000;
	
	cout << "The worst-case time, in milliseconds, are" << endl;
	cout << "n \tRepetitions \tTotal Ticks \tTime Per Sort" << endl;
	
	for (int n = 0; n <= 2000; n += step) {
		long numOfRepetitions = 0;
		clock_t startTime = clock();
		a = new int*[n];
		b = new int*[n];
		c = new int*[n];
        int ix;
		for (ix = 0; ix < n; ix ++) {
			a[ix] = new int[n];
			b[ix] = new int[n];
			c[ix] = new int[n];
			if ( a[ix] == NULL || b[ix] == NULL || c[ix] == NULL)
			   exit(1);
		}

		do{
			numOfRepetitions ++;
            
			// the badest states
		    for (int i = 0; i < n; i++){
				for (int j = 0; j < n; j++) {
                     a[i][j] = rand()%10;
                     b[i][j] = rand()%20;
				}                
			}
			    
			
			matrixMultiplyHigh(a, b, c, n);
		}while(clock() - startTime < 1000);

		double elapsed = (clock() - startTime)/clocks;	
		cout << n << '\t' << numOfRepetitions << '\t' << elapsed 
		     << '\t' << elapsed/numOfRepetitions << endl;
		if (n == 100)
			step = 100;	
		else if (n == 1000)
		    step = 500;		

		for (ix = 0; ix < n; ix++) {
			delete [] a[ix];
			delete [] b[ix];
			delete [] b[ix];
		}  

		delete [] a;
		delete [] b;
		delete [] c;   
	}
}